/**
 * Copyright (c) [2025] [何屹林]
 *
 * 保留所有权利。
 *
 * 文件名称：LR1.cpp
 * 模块功能说明：
 * 该模块实现LR1相关分析，定义生成LR1内容的各种函数，并构建LR1状态表和转移表。
 *
 * 华南师范大学-计算机学院-网络工程-1班
 * 作者：何屹林-20222132023
 * 完成日期：2025年7月24日
 */
#include "LR1.h"

bool State::haveSameCore(State i, State j)
{
    if(i.st.size()!=j.st.size()) return false;
    QList<Item> t1;
    QList<Item> t2;
    for(auto it:i.st)
        t1.append(it);
    for(auto it:j.st)
        t2.append(it);
    for(int k=0;k<i.st.size();k++)
        if(!Item::haveSameCore(t1[k],t2[k])) return false;
    return true;
}

bool Item::haveSameCore(Item i, Item j)
{
    return i.name==j.name&&i.pos==j.pos&&i.rule==j.rule;
}

State State::closure(State I,QHash<QString, QSet<QStringList>> grammars
                     ,QVector<QString> nonFinalizers, QHash<QString, QSet<QString>> first_set)
{//伊普西隆闭包，从一个部分状态I生成LR1的完整的状态

    State J = I;
    bool changed;
    do {
        changed = false;
        State newItems; // 用于暂存本轮迭代新增的项
        QHash<Item, QSet<QString>> coreMap;

        for (const Item& item : qAsConst(J.st)) {
            Item coreItem(item.name, item.rule, QSet<QString>(), item.pos);
            coreMap[coreItem].unite(item.next);
        }

        // 遍历当前状态中的所有项
        for (const Item& item : qAsConst(J.st)) {
            if (item.pos >= item.rule.size() || !nonFinalizers.contains(item.rule[item.pos]))
                continue;

            QString A = item.rule[item.pos]; // 当前非终结符
            const QStringList& beta = item.rule.mid(item.pos + 1); // A后面的符号序列β
            const QSet<QString>& lookaheads = item.next; // 原始向前看符号集合

            // 遍历该非终结符的所有产生式 A -> γ
            for (const QStringList& production : grammars[A]) {
                // 计算 FIRST(βa) ，其中a是原始向前看符号
                QSet<QString> first_beta_a;

                bool allNullable = true;
                for (const QString& symbol : beta) {
                    QSet<QString> tempFirstSet=first_set[symbol];
                    first_beta_a.unite(tempFirstSet.subtract({"@"}));
                    if (!first_set[symbol].contains("@")) {
                        allNullable = false;
                        break;
                    }
                }

                if (allNullable) {
                    first_beta_a.unite(lookaheads);
                }

                first_beta_a.remove("@");

                // 为每个b创建新项
                for (const QString& b : first_beta_a) {
                    Item newItem(A, production, QSet<QString>(), 0);

                    auto it_newItem=coreMap.find(newItem);

                    if (it_newItem == coreMap.end()) {
                        coreMap[newItem] = {b};
                        changed = true;
                    } else if (!it_newItem.value().contains(b)) {
                        it_newItem.value().insert(b);
                        changed = true;
                    }
                }
            }
        }

        J.st.clear();
        for (auto it = coreMap.begin(); it != coreMap.end(); ++it) {
            Item item = it.key();
            item.next = it.value();
            J.st.insert(item);
            //            qDebug()<<item.name<<item.rule<<item.next;
        }

    } while (changed); // 直到闭包不再变化

    return J;
}

State State::change(State I, QString X, QHash<QString, QSet<QStringList>> grammars, QVector<QString> nonFinalizers, QHash<QString, QSet<QString>> first_set)
//移进项X会对状态I产生什么影响，是否需要规约等等
{
    State I_new;

    QHash<Item, QSet<QString>> coreMap; // Key: 核心项（name, rule, pos）, Value: 合并后的next集合

    // 第一遍：收集所有核心项及其next集合
    for (const Item& item : I.st) {
        if (item.pos >= item.rule.size() || item.rule[item.pos] != X)
            continue;

        // 生成移进后的核心项（pos+1，忽略next）
        Item newItem(item.name, item.rule, QSet<QString>(), item.pos + 1);
        coreMap[newItem].unite(item.next); // 合并next集合
    }

    // 第二遍：将核心项和合并后的next写入I_new.st
    for (auto it = coreMap.begin(); it != coreMap.end(); ++it) {
        Item newItem = it.key();
        newItem.next = it.value();
        I_new.st.insert(newItem);
    }

    if (I_new.st.empty()) return I_new;
    else return closure(I_new, grammars, nonFinalizers, first_set);
}

int getProductionIndex(const QString& nonTerminal, const QStringList& production,
                       QVector<Gram> grammars) {
    int index = 0;
    for (const Gram& prod : grammars) {
        if (prod.l == nonTerminal && prod.r == production) return index;
        index++;
    }
    return -1; // 未找到（理论上不应发生）
}

void LR1::buildLR1(State cur_state, QHash<QString, QSet<QStringList>> grammars, QVector<QString> nonFinalizers,
                   QHash<QString, QSet<QString>> first_set, QHash<QString, QSet<QString>> follow_set,QVector<Gram> Grams)
{
    int cur_state_id = state_hash[cur_state];

    //存储归约动作
    for (const Item& item : cur_state.st) {
        if (item.pos == item.rule.size()) {  // 可归约项
            for (const QString& a : item.next) {
                reduce_hash[cur_state_id][a] = getProductionIndex(item.name, item.rule,Grams);
            }
        }
    }

    // 找到可能的转移方法
    QStringList changeMethods;
    for (auto item: cur_state.st) {
        if (item.pos < item.rule.size()) {
            QString symbol = item.rule[item.pos];
            if (!changeMethods.contains(symbol)) {
                changeMethods.append(symbol);
            }
        }
    }

    // 深搜每个转移
    for (QString changeMethod: changeMethods)
    {
        State sub_state = State::change(cur_state, changeMethod, grammars, nonFinalizers, first_set);//！！！！

        if (sub_state.st.empty()) continue;
        if (state_hash.contains(sub_state))//若状态存在，则指向其，若不存在，则创建新的状态并指向其
        {
            // 该状态已经存在
            int sonStateId = state_hash[sub_state];
            change_hash[cur_state_id].insert(changeMethod, sonStateId);
        } else {
            // 该状态不存在
            state_hash[sub_state] = size++;
            change_hash[cur_state_id].insert(changeMethod, state_hash[sub_state]);
            buildLR1(sub_state, grammars, nonFinalizers, first_set, follow_set,Grams);
        }
    }
}

size_t qHash(const State &key)
{
    return qHash(key.st);
}


